package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第354场单周赛 {

    public static void main(String[] args) {

        System.out.println(maximumBeauty(new int[]{4, 6, 1, 2}, 2));

        List<Integer> list = new ArrayList<>();
        int[] nums = {2, 1, 3, 1, 1, 1, 7, 1, 2, 1};
        for (int num : nums) {
            list.add(num);
        }
        System.out.println(minimumIndex(list));

        System.out.println(longestValidSubstring("aaaabaaacc", Arrays.asList("bcca", "aaa", "aabaa", "baaac")));

    }

    /**
     * 排序+滑动窗口
     * 窗口内的最大值-最小值 <= 2*k
     */
    public static int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0;
        int l = 0;
        for (int r = 0; r < nums.length; r++) {
            while (l < r && nums[r] - nums[l] > 2 * k) {
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }

    /**
     * 投票算法+前缀和
     */
    public static int minimumIndex(List<Integer> nums) {
        // 投票算法，选出出现次数最多的数
        int freqNum = nums.get(0), cnt = 1;
        for (Integer num : nums) {
            if (num == freqNum) {
                cnt++;
            } else if (cnt > 1) {
                cnt--;
            } else {
                freqNum = num;
            }
        }
        // 前缀和
        int[] prefixSum = new int[nums.size() + 1];
        for (int i = 0; i < nums.size(); i++) {
            prefixSum[i + 1] = prefixSum[i];
            if (nums.get(i) == freqNum) {
                prefixSum[i + 1]++;
            }
        }

        for (int i = 0; i < nums.size(); i++) {
            if (prefixSum[i + 1] * 2 > i + 1 &&
                    (prefixSum[nums.size()] - prefixSum[i + 1]) * 2 > nums.size() - i - 1) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 双指针+哈希表
     * 注意：1 <= forbidden[i].length <= 10
     */
    public static int longestValidSubstring(String word, List<String> forbidden) {
        Set<String> forbiddenSet = new HashSet<>(forbidden);
        int ans = 0;
        int left = 0;
        for (int right = 0; right < word.length(); right++) {
            for (int l = right; l >= left && right - l + 1 <= 10; l--) {
                if (forbiddenSet.contains(word.substring(l, right + 1))) {
                    left = l + 1;
                    break;
                }
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
